#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

 

示例 1:


输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

// TODO 这个题自己没有任何思路  法克鱿
//感觉像求层次遍历
/*
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
 *
 * */
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

    if (postorder.size()==0)
        return nullptr;

    int midVal=postorder[postorder.size()-1];//获取最后一个元素也就是根节点
    TreeNode* root=new  TreeNode(midVal);

    //post 或者inorder 都可以吧
    if (postorder.size()==1)
        return root;
    //获取中序的左边和右边

    int midIndex=0;
    for (int i = 0; i <inorder.size() ; ++i) {
        if (inorder[i]==midVal)
        {
            midIndex=i;
            break;
        }
    }



    vector<int> inorderSubLeft(inorder.begin(),inorder.begin()+midIndex);//分割的前序子数组左边

    vector<int> inorderSubRight(inorder.begin()+midIndex+1,inorder.end());//分割的前序子数组右边

    //获取后序元素的sub
    postorder.resize(postorder.size()-1);//除去最后一个元素

    vector<int> postorderSubLeft(postorder.begin(),postorder.begin()+inorderSubLeft.size());

    vector<int> postorderSubRight(postorder.begin()+inorderSubLeft.size(),postorder.end());

    root->left=buildTree(inorderSubLeft,postorderSubLeft);

    root->right=buildTree(inorderSubRight,postorderSubRight);

    return root;
}